package 蓝桥真题;

import java.util.Arrays;

public class 路径 {
       final static int N=2031;
       static int g[][]=new int[N][N],dist[]=new int[N];
       static boolean st[]=new boolean[N];
       static int gcd(int a,int b){
    	      return b>0?gcd(b,a%b):a;
       }
       static void dijkstra(){
    	      Arrays.fill(dist,0x3f3f3f3f);      
    	      dist[1]=0;
    	      for(int i=0;i<2021;i++){
    	    	  int t=-1;
    	    	  for(int j=1;j<=2021;j++)
    	    		  if(!st[j]&&(t==-1||dist[j]<dist[t]))
    	    			  t=j;
    	    	  st[t]=true;
    	    	  for(int j=1;j<=2021;j++)
    	    		  dist[j]=Math.min(dist[j],dist[t]+g[t][j]);
    	      }
    	      System.out.print(dist[2021]);
       }
       public static void main(String[]args){
    	      for(int i=1;i<=2021;i++)
    	    	  Arrays.fill(g[i],0x3f3f3f3f);
    	      for(int i=1;i<=2021;i++){
    	    	  for(int j=i+1;j<=2021;j++){
    	    		  if(Math.abs(i-j)<=21){
    	    			  int t=(i*j)/gcd(i,j);
        	    		  g[i][j]=t;g[j][i]=t;
    	    		  }
    	    	  }
    	      }
    	      dijkstra();
       }
}
